perm filename SHORT.PAP[L70,TES] blob
sn#009949 filedate 1972-07-08 generic text, type T, neo UTF8
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃ THE PROGRAMMING LANGUAGE "LISP70"
␈⊃
␈⊃ LAWRENCE G. TESLER, HORACE J. ENEA, AND DAVID C. SMITH
␈⊃
␈⊃ STANFORD UNIVERSITY
␈⊃ ARTIFICIAL INTELLIGENCE PROJECT
␈⊃
␈⊃ FEBRUARY, 1972
␈⊃ LISP70 July 8, 1972
␈⊃
␈⊃
␈⊃ INTRODUCTION
␈⊃
␈⊃
␈⊃
␈⊃ The language LISP [ref McCarthy] deals with recursive functions of symbolic
␈⊃expressions. There has recently emerged a trend towards creating "New LISPs"
␈⊃offering additional capabilities. Of primary interest are expanded control
␈⊃structures, including backtracking and multiple processing. Also of importance
␈⊃are varied methods of data access, such as associative data bases. The question
␈⊃of an appropriate successor to LISP is discussed elsewhere [ref Bobrow].
␈⊃
␈⊃ Some of the "New LISPs" that are currently under development are PLANNER at
␈⊃MIT [ref Hewitt], QA-4 at SRI [ref Rulifson], POP-2 at ?? [ref ??], and LISP70,
␈⊃the subject of the present paper. Having evolved separately, they differ
␈⊃somewhat in detail. However, their similarities are more striking than their
␈⊃differences. All provide convenient vehicles for theorem proving, robot
␈⊃planning, natural language processing, and other complex problem solving tasks.
␈⊃
␈⊃ LISP70 is distinguished from the other "New LISPs" primarily by its
␈⊃extendability. The design goals of the language, in approximate order of
␈⊃importance, are:
␈⊃
␈⊃ (1) Extendability
␈⊃ (2) Inter-machine transferability
␈⊃ (3) Facilitated debugging
␈⊃ (4) Convenient input and output
␈⊃ (5) Efficiency of operation
␈⊃
␈⊃Each of these goals will be discussed separately.
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃ 1
␈⊃ LISP70 July 8, 1972
␈⊃
␈⊃
␈⊃ EXTENDABILITY
␈⊃
␈⊃
␈⊃
␈⊃ Every extendable language consists of a "core" and a method of extending
␈⊃that core. The core of LISP70 is actually much larger than necessary; that is,
␈⊃most parts of the core are defined in terms of more primitive parts. Some of
␈⊃the facilities offered are:
␈⊃
␈⊃ (1) LISP 1.5, a common standard [ref]
␈⊃ (2) MLISP, an Algol-like M-expression notation [ref Enea, ref Smith]
␈⊃ (3) Automatic Backtracking [ref Floyd]
␈⊃ (4) Pattern-Directed Computation
␈⊃ (5) Syntax-Directed Input-Output
␈⊃ (6) Extensive monitoring capabilities
␈⊃ (7) A variety of data types
␈⊃ (8) "Extendable Functions"
␈⊃
␈⊃
␈⊃ An Extendable Function is a function which is defined by an open-ended set
␈⊃of "rewrite rules" [ref somebody]. The "EXTEND Statement" adds new rules to an
␈⊃Extendable Function. The LISP70 compilers are defined primarily in terms of
␈⊃Extendable Functions. Thus, anyone can extend them by use of appropriate EXTEND
␈⊃Statements. The scope of an extension can be a whole program or any part of a
␈⊃program.
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃ 2
␈⊃ LISP70 July 8, 1972
␈⊃
␈⊃
␈⊃ EXTENDING MLISP
␈⊃
␈⊃
␈⊃
␈⊃ MLISP is defined entirely by Extendable Functions such as "EXPRESSION",
␈⊃which translates an M-expression to an S-expression. For example, the
␈⊃conditional expression of MLISP is defined in terms of the conditional
␈⊃expression of LISP by the following rewrite rule in EXPRESSION:
␈⊃
␈⊃ ⊂IF <expression>:e1 THEN <expression>:e2 ELSE <expression>:e3⊃
␈⊃ →→ (COND (:e1 :e2) (T :e3))
␈⊃
␈⊃Every rewrite rule has a left side and a right side separated by right-pointing
␈⊃arrows. A rewrite rule can translate any input that matches its left side to an
␈⊃output constructed by its right side. Strictly local variables (preceded by the
␈⊃character ":") serve to carry information from the left side to the right side.
␈⊃
␈⊃ The above rule for translating conditionals is read from left to right as
␈⊃follows:
␈⊃
␈⊃ An input stream ("⊂...⊃") which begins with the symbol
␈⊃ `IF', followed by an <expression> (whose translation is
␈⊃ bound to e1), followed by `THEN', followed by another
␈⊃ <expression> (whose translation is bound to e2), followed by
␈⊃ `ELSE', followed by another <expression> (whose translation
␈⊃ is bound to e3), can definitely ("→→") be rewritten as a
␈⊃ list of the following three elements: first, the symbol
␈⊃ `COND'; second, a list containing the binding of e1 and the
␈⊃ binding of e2; finally, a list containing `T' and the
␈⊃ binding of e3.
␈⊃
␈⊃
␈⊃ Each of the three occurrences of <expression> within this definition calls
␈⊃EXPRESSION recursively to translate portions of the conditional. Should any of
␈⊃these calls fail, the entire rewrite rule fails and a different rule of
␈⊃EXPRESSION is tried. Thus, more than one rule of the syntax may begin with the
␈⊃symbol `IF'. In fact, it is possible to define arbitrarily context-sensitive
␈⊃grammars with LISP70 rewrite rules, but this subject will not be explored here.
␈⊃
␈⊃ As an illustration of the operation of the above rewrite rule, the
␈⊃processing of the following input stream will be traced:
␈⊃
␈⊃ if a=b then 7 else cons(7,a)
␈⊃
␈⊃After `IF' is matched, `a=b' is translated by a recursive call on EXPRESSION to
␈⊃`(EQUAL A B)', which is bound to e1. The other local variables are bound in a
␈⊃similar manner, yielding:
␈⊃
␈⊃
␈⊃ 3
␈⊃ LISP70 EXTENDING MLISP
␈⊃
␈⊃
␈⊃
␈⊃ e1 = (EQUAL A B)
␈⊃ e2 = 7
␈⊃ e3 = (CONS 7 A)
␈⊃
␈⊃These bindings are substituted into the right hand side, outputting the
␈⊃translation:
␈⊃
␈⊃ (COND ((EQUAL A B) 7) (T (CONS 7 A)) )
␈⊃
␈⊃
␈⊃ Example:
␈⊃
␈⊃ extendable function simplify =
␈⊃ (PLUS 0 ::X) →→ (PLUS ::X)*,
␈⊃ (PLUS :A ::B) →→ (PLUS :A (PLUS ::B)*@@CDR),
␈⊃ (PLUS) →→ 0 ;
␈⊃
␈⊃
␈⊃ Some notation must be explained:
␈⊃
␈⊃ :X Matches any one item and binds it to X.
␈⊃ :X On right side: the binding of X.
␈⊃ ::X Matches zero or more items, forms them into
␈⊃ a list, binds that list to X.
␈⊃ ::X On right side: the elements of X, i.e., the list
␈⊃ X with its outer parentheses stripped.
␈⊃ @F Postfix Function Call: Call function F with the
␈⊃ preceding value as its argument, e.g.,
␈⊃ ((A) B C)@CAR yields (A).
␈⊃ @@F Call F and strip the result, e.g.,
␈⊃ ((A) B C)@@CAR yields A.
␈⊃ * Call the current function recursively, i.e.,
␈⊃ same as @SIMPLIFY.
␈⊃ ** In this case, same as @@SIMPLIFY.
␈⊃ (...) Match or construct a list.
␈⊃ ⊂...⊃ Match or construct a stream.
␈⊃ `...' Same as ⊂...⊃, but no special characters are
␈⊃ recognized except <>*@:
␈⊃
␈⊃
␈⊃ Let us trace the call (SIMPLIFY (QUOTE (PLUS HAT 0 J K))).
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃ 4
␈⊃ LISP70 EXTENDING MLISP
␈⊃
␈⊃
␈⊃
␈⊃ Argument Rule Applied Result
␈⊃ -------- ---- ------- ------
␈⊃
␈⊃ (PLUS HAT 0 J K)) 2 (PLUS HAT (PLUS 0 J K)*@@CDR)
␈⊃ (PLUS 0 J K) 1 (PLUS J K)*
␈⊃ (PLUS J K) 2 (PLUS J (PLUS K)*@@CDR)
␈⊃ (PLUS K) 2 (PLUS K (PLUS)*@@CDR)
␈⊃ (PLUS) 3 (PLUS)
␈⊃
␈⊃ Expression After * After CDR After STRIP
␈⊃ ---------- ------- --------- -----------
␈⊃
␈⊃ (PLUS)*@@CDR (PLUS)@@CDR ()@STRIP ⊂ ⊃
␈⊃ (PLUS K)*@@CDR (PLUS K)@@CDR (K)@@STRIP K
␈⊃ (PLUS 0 J K)*@@CDR (PLUS J K)@@CDR (J K)@STRIP J K
␈⊃
␈⊃When several rules occur in an extendable function, they are ordered Most
␈⊃Specific First. If the left side of the first rule matches the input, then the
␈⊃value of the function is computed by the right side of that rule. Otherwise,
␈⊃subsequent rules are tried in the same way. If no rule matches, a failure
␈⊃occurs, causing backtracking.
␈⊃
␈⊃ Proper ordering of rules is important both for speed and correctness. In
␈⊃the compiler, the Most Specific First heuristic is trivial to implement. For
␈⊃example, if the left sides of two rules are identical up to a point at which one
␈⊃has a literal symbol and the other has a local variable binding, then the former
␈⊃rule is ordered before the latter. This is because the literal symbol can only
␈⊃match one possible input entity while the local variable binding can match
␈⊃anything.
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃
␈⊃ 5
␈⊃